package basic.study.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Mid78
 * @Description 子集
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/24 10:51
 * @Version 1.0
 */
public class Mid78 {
    /**
     * 递归
     */
    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> output = new ArrayList<>();
            output.add(new ArrayList<>());

            for (int num: nums) {
                List<List<Integer>> newSubsets = new ArrayList<>();
                for (List<Integer> curr : output) {
                    newSubsets.add(new ArrayList<Integer>(curr){{add(num);}});
                }
                for (List<Integer> curr: newSubsets) {
                    output.add(curr);
                }
            }
            return output;
        }
    }

    /**
     * 回溯
     */
    class Solution1 {
        int n, k;
        List<List<Integer>> res = new ArrayList<>();

        public void backtrack(int first, ArrayList<Integer> curr, int[] nums) {
            if (curr.size() == k) {
                res.add(curr);
                return;
            }

            for (int i = first; i < nums.length; i++) {
                curr.add(nums[i]);
                backtrack(i+1, curr, nums);
                curr.remove(curr.size()-1);
            }
        }

        public List<List<Integer>> subsets(int[] nums) {
            n = nums.length;
            for (k = 0; k < nums.length + 1; k++) {
                backtrack(0, new ArrayList<Integer>(), nums);
            }
            return res;
        }
    }
    /**
     * 字典排序
     */
    class Solution2 {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> output = new ArrayList<>();
            int n = nums.length;

            for (int i = (int)Math.pow(2, n); i < (int)Math.pow(2, n+1); i++) {
                //Generate Mask
                String bitmask = Integer.toBinaryString(i).substring(1);

                List<Integer> curr = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if (bitmask.charAt(j) == '1') {
                        curr.add(nums[j]);
                    }
                }
                output.add(curr);
            }
            return output;
        }
    }
}
